""" 欢迎关注 "码农架构" 微信公众号，热爱开源，拥抱开源。一个IT民工的技术之路经验分享。
    - 问题咨询 / 建议
    1.关注微信公众号 "码农架构" 后私信
    2.可发送邮件: li.shangzhi@aliyun.com
"""
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/12/27 23:44
# @Author  : iByte

# 1. 用扩展欧几里德算法求解 x,y such that a*x + b*y = 1
# 2. Take n = ra*by + rb*ax

def extended_euclid(a, b):
    """
    >>> extended_euclid(10, 6)
    (-1, 2)
    >>> extended_euclid(7, 5)
    (-2, 3)
    """
    if b == 0:
        return (1, 0)
    (x, y) = extended_euclid(b, a % b)
    k = a // b
    return (y, x - k * y)


# 使用扩展到反向
def chinese_remainder_theorem(n1, r1, n2, r2):
    """
    >>> chinese_remainder_theorem(5,1,7,3)
    31
    说明：31是最小的数字，因此
        （i） 当我们把它除以5，我们得到余数1
        （ii）当我们把它除以7，我们得到余数3
    >>> chinese_remainder_theorem(6,1,4,3)
    14
    """
    (x, y) = extended_euclid(n1, n2)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m


# ----------用逆模代替扩展欧几里德的同一解----------------

# 这个函数找到 a i.e., a^(-1)
def invert_modulo(a, n):
    """
    >>> invert_modulo(2, 5)
    3
    >>> invert_modulo(8,7)
    1
    """
    (b, x) = extended_euclid(a, n)
    if b < 0:
        b = (b % n + n) % n
    return b


# 与上面的a相同，使用反转模
def chinese_remainder_theorem2(n1, r1, n2, r2):
    """
    >>> chinese_remainder_theorem2(5,1,7,3)
    31
    >>> chinese_remainder_theorem2(6,1,4,3)
    14
    """
    x, y = invert_modulo(n1, n2), invert_modulo(n2, n1)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m


# 导入testmod以测试我们的函数
from doctest import testmod

if __name__ == "__main__":
    testmod(name="chinese_remainder_theorem", verbose=True)
    testmod(name="chinese_remainder_theorem2", verbose=True)
    testmod(name="invert_modulo", verbose=True)
    testmod(name="extended_euclid", verbose=True)